import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author ZCR
 * @create 2025/9/4 21:05
 * 前序遍历：中，左，右
 * 中序遍历：左，中，右
 * 后序遍历：左，右，中
 * <p>
 * 本题需要中序遍历。
 * <p>
 * 栈是一种 先进后出的结构，出栈顺序为左，中，右
 * 那么入栈顺序必须调整为倒序，也就是右，中，左
 * <p>
 * 同理，如果是前序遍历，入栈顺序为 右，左，中；后序遍历，入栈顺序中，右，左
 * 其核心思想如下：
 *
 * 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
 * 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
 * 如果遇到的节点为灰色，则将节点的值输出。
 *
 * 作者：henry
 * 链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/25220/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class Solution94 {
    public enum COLOR {
        WHITE, GRAY;
    }

    public static class ColorNode {
        COLOR color;//0 是白色,1是灰色
        TreeNode node;

        public ColorNode(COLOR color, TreeNode node) {
            this.color = color;
            this.node = node;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(COLOR.WHITE, root));
        while (!stack.isEmpty()) {
            ColorNode node = stack.pop();
            if (node.node != null) {
                if (node.color == COLOR.WHITE) {
                    stack.push(new ColorNode(COLOR.WHITE, node.node.right));//右
                    stack.push(new ColorNode(COLOR.GRAY, node.node));//根
                    stack.push(new ColorNode(COLOR.WHITE, node.node.left));//左
                } else {
                    res.add(node.node.val);
                }
            }
        }
        return res;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(COLOR.WHITE, root));
        while (!stack.isEmpty()) {
            ColorNode node = stack.pop();
            if (node.node != null) {
                if (node.color == COLOR.WHITE) {
                    stack.push(new ColorNode(COLOR.WHITE, node.node.right));//右
                    stack.push(new ColorNode(COLOR.WHITE, node.node.left));//左
                    stack.push(new ColorNode(COLOR.GRAY, node.node));//根
                } else {
                    res.add(node.node.val);
                }
            }
        }
        return res;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(COLOR.WHITE, root));
        while (!stack.isEmpty()) {
            ColorNode node = stack.pop();
            if (node.node != null) {
                if (node.color == COLOR.WHITE) {
                    stack.push(new ColorNode(COLOR.GRAY, node.node));//根
                    stack.push(new ColorNode(COLOR.WHITE, node.node.right));//右
                    stack.push(new ColorNode(COLOR.WHITE, node.node.left));//左
                } else {
                    res.add(node.node.val);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution94 solution = new Solution94();
        TreeNode root = TreeNode.buildTree(new int[]{1, -1, 2, 3}, -1);
        System.out.println(solution.inorderTraversal(root));
        System.out.println(solution.preorderTraversal(root));
        System.out.println(solution.postorderTraversal(root));
        System.out.println("--------------------");
        System.out.println(solution.inorderTraversal(null));
        root = TreeNode.buildTree(new int[]{1}, -1);
        System.out.println(solution.inorderTraversal(root));

    }
}
